package com.chj.zhongji.class04;

public class Code06_LCSubstring {
//	https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/submissions/
	public static String lcst1(String str1, String str2) {
		if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
			return "";
		}
		char[] chs1 = str1.toCharArray();
		char[] chs2 = str2.toCharArray();
		int[][] dp = getdp(chs1, chs2);

		printMatrix(dp);

		int end = 0;
		int max = 0;
		for (int i = 0; i < chs1.length; i++) {
			for (int j = 0; j < chs2.length; j++) {
				if (dp[i][j] > max) {
					end = i;
					max = dp[i][j];
				}
			}
		}
//		"KC12D"
		System.out.println(end + "--end" + "---" + max);
		return str1.substring(end - (max - 1), end + 1);
	}

	public static int[][] getdp(char[] str1, char[] str2) {
		int[][] dp = new int[str1.length][str2.length];
		for (int i = 0; i < str1.length; i++) {
			if (str1[i] == str2[0]) {
				dp[i][0] = 1;
			}
		}

//		System.out.println("-----111-------");
//		printMatrix(dp);
//		System.out.println("-----111-------");

		for (int j = 1; j < str2.length; j++) {
			if (str1[0] == str2[j]) {
				dp[0][j] = 1;
			}
		}

//		System.out.println("-----222-------");
//		printMatrix(dp);
//		System.out.println("-----222-------");

		for (int i = 1; i < str1.length; i++) {
			for (int j = 1; j < str2.length; j++) {
				if (str1[i] == str2[j]) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
//					System.out.println(i + "==iijj===" + j);
//					System.out.println(str1[i] + "=====" + str2[j] + "-----333-------");
//					System.out.println(dp[i - 1][j - 1] + "=====" + dp[i][j] + "-----444-------");
				} else {
					dp[i][j] = 0;
				}
			}
		}
		return dp;
	}

	public static String lcst2(String str1, String str2) {
		if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
			return "";
		}
		char[] chs1 = str1.toCharArray();
		char[] chs2 = str2.toCharArray();
		int row = 0;
		int col = chs2.length - 1;
		int max = 0;
		int end = 0;
		while (row < chs1.length) {
			int i = row;
			int j = col;
			int len = 0;

			while (i < chs1.length && j < chs2.length) {
				if (chs1[i] != chs2[j]) {
					len = 0;
				} else {
					len++;
				}
				if (len > max) {
					end = i;
					max = len;
				}
				i++;
				j++;
			}
			if (col > 0) {
				col--;
			} else {
				row++;
			}
		}
		return str1.substring(end - max + 1, end + 1);
	}

	public int findLength(int[] A, int[] B) {
		int[][] dp = new int[A.length][B.length];
		for (int i = 0; i < A.length; i++) {
			if (A[i] == B[0]) {
				dp[i][0] = 1;
			}
		}

		for (int j = 1; j < B.length; j++) {
			if (A[0] == B[j]) {
				dp[0][j] = 1;
			}
		}

		int res = 0;
		for (int i = 1; i < A.length; i++) {
			for (int j = 1; j < B.length; j++) {
				if (A[i] == B[j]) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					dp[i][j] = 0;
				}
				res = Math.max(res, dp[i][j]);
			}
		}
		return res;
	}

	// for test
	public static void printMatrix(int[][] matrix) {
		for (int i = 0; i != matrix.length; i++) {
			for (int j = 0; j != matrix[0].length; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
//		String str1 = "ABC1234567DEFG";
//		String str2 = "HIJKL1234567MNOP";

		String str1 = "KC12D";
		String str2 = "CKJ12PH";
		System.out.println(lcst1(str1, str2));
		System.out.println(lcst2(str1, str2));

	}
}
